package findingTheNumberOfVisibleMountains_2345;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Stack;

//https://leetcode.cn/problems/finding-the-number-of-visible-mountains/
class Solution {
    public static int visibleMountains(int[][] peaks) {
        Info[] temp = new Info[peaks.length];
        for (int i = 0; i < peaks.length; i++) {
            temp[i] = new Info(peaks[i]);
        }

        Arrays.sort(temp, Comparator.comparingInt(o -> o.left));
        Stack<Info> stack = new Stack<>();
        for (Info info : temp) {
            if (stack.isEmpty()) {
                stack.add(info);
                continue;
            }
            Info top = stack.peek();
            // 相同起点在栈顶一定只会出现一次
            if (top.left == info.left && top.height == info.height) {
                stack.pop();
                continue;
            }
            if (top.left == info.left && top.height < info.height) {
                stack.pop();
                stack.add(info);
                continue;
            }
            if (top.left == info.left) {
                continue;
            }
            if (info.height >= top.height) {
                stack.add(info);
                continue;
            }
            if (info.left - top.left > (top.height - info.height) * 2) {
                stack.add(info);
            }
        }
        return stack.size();
    }

    public static void main(String[] args) {
//        System.out.println(visibleMountains(new int[][]{new int[]{3, 19}, new int[]{39, 7}, new int[]{15, 39}, new int[]{23, 13}, new int[]{8, 28}, new int[]{2, 26}, new int[]{38, 15}, new int[]{38, 7}, new int[]{16, 17}}));
        System.out.println(visibleMountains(new int[][]{new int[]{2, 2}, new int[]{2, 2}, new int[]{3, 1}}));
    }
}

class Info {
    int left;
    int mid;
    int height;

    public Info(int[] info) {
        this.left = info[0] - info[1];
        this.height = info[1];
        this.mid = info[0];
    }
}
